package BFS解决拓扑排序;

import java.util.*;

public class test2 {
    public int[] findOrder(int n, int[][] p) {
        // 1.创建
        int[] in = new int[n];
        Map<Integer, List<Integer>> edges = new HashMap<>();

        // 2.建图
        for (int i = 0; i < p.length; i++) {
            int a=p[i][0],b=p[i][1];
            if(!edges.containsKey(b)) edges.put(b,new ArrayList<>());
            edges.get(b).add(a);
            in[a]++; //统计入度
        }

        // 3.遍历排序
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if(in[i]==0) queue.add(i);
        }

        int[] result = new int[n];
        int index=0;
        while (!queue.isEmpty()){
            int t = queue.poll();
            result[index++] = t;
            for(int x:edges.getOrDefault(t,new ArrayList<>())){
                in[x]--;
                if(in[x]==0) queue.add(x);
            }
        }

        // 处理
        if(index==n) return result;
        return new int[0];
    }
}
